Data communication systems employing packet switching strategies can offer desirable advances in resource utilization and reliability with minimal losses in delivery speed. Digital data is divided into packets, each of which is routed independently to its destination. Access to, routing within and delivery from the network for the packets is mediated by a framework of routers, adapters, switches and other network nodes, generally termed the switching fabric. This configuration allows the network to dynamically adjust to the demands of varying traffic patterns. As will be appreciated, an important consideration in the design of such networks is the efficient use of inputs and outputs, so that an adequate number are available to provide the desired level of throughput without incurring the expense of providing an excess that go underutilized for significant periods of time. A primary technique for allocating network resource to achieve this minimization of contention and avoidance of starvation is the use of buffers and queues to asynchronously transmit the data streams of packets.
A typical approach to facilitate the routing and switching of the individual data packets is to employ the use of descriptors that identify the destination of each packet and its storage location within the memory of the network. Since the descriptors can be significantly smaller than the packets themselves, manipulating the descriptors provides important savings in processing time and storage requirements.
Despite the advantages, packet switching systems cannot rely on a dedicated connection between two points on the network, such as that offered by circuit switching systems. Thus, each packet in a given data stream potentially experiences different latencies and transmission rates, resulting in the possibility that packets will arrive at the destination at of order or that some packets may be dropped. These concerns are less important when dealing with static files, but for the streaming delivery of multimedia content or real time communication applications, for example, robust and timely delivery of the packets is a priority. To maintain adequate quality of service (QoS) for such applications, techniques have been developed to assign varying priority levels to the packets of data. Accordingly, the buffering and queuing process carried out within the switching fabric must be able to implement these priorities in the delivery of data. In systems employing descriptors, the priority information is included along with the location and destination information recorded by the descriptor.
Another challenge in the implementation of packet switched networks is the distinction between unicast data and multicast data. As indicated by the name, unicast data deals with information being delivered from a single sender to a single recipient. Thus, unicast packets consume one input port and one output port of the switching fabric. On the other hand, multicast data can originate from one or more senders and be delivered to one or more recipients. Generally, the multicast packets are replicated during the delivery process by the network and are fanned-out to the desired output ports. Generally, in modern networks, each node comprises N bidirectional ports, each allowing for inbound or outbound traffic. In the worst case scenario, a single multicast packet may consume only a single input port but consume all available outgoing ports (N−1), leading to starvation of traffic. Again, the buffering and queuing strategies employed by the network system should accommodate these situations to allow for “fair” scheduling of unicast and multicast traffic to prevent starvation of one type.
One prior art technique is disclosed in U.S. Pat. No. 7,397,809 to Wang. The implementation disclosed in this reference makes use of hybrid queue composed of a linked list of descriptors for unicast data and a first in, first out (FIFO) buffer of pointers for multicast descriptors. To schedule between multicast and unicast traffic, the system employs an arrival counter, a departure counter and each multicast FIFO entry has an inter-departure-counter value specifying the number of unicast linked list entries that have to be serviced before servicing the multicast FIFO entry.
Despite the advantages offered by this approach, it does suffer from certain drawbacks. Specifically, the scheduling between the unicast and multicasts depends upon the counters, the inter-departure-counter for each multicast FIFO entry and the arrival and departure counters for each queue. This requirement prevents the system from scaling well with variable length queues. Furthermore, the Wang reference requires the use of a fixed multicast FIFO entry for every queue. As one of skill in the art will recognize, this does not represent the most efficient use of memory space, since each FIFO buffer requires a fixed amount of space. Similarly, this makes the system less scalable for worst case tolerance.
Therefore, it would be desirable to provide systems and methods that allow for efficient and scalable scheduling of multicast and unicast packetized data traffic. It would also be desirable to provide systems and methods for providing such scheduling while minimizing the overhead imparted to output queues. Finally, it would be desirable to provide such systems and methods that enable the use of multiple data structures for multicast queues.